This invention relates to telecommunication and more particularly to multiple access telecommunication and even more particularly to cellular radio telephone communication. This invention enables a first party electronically to verify the identity of a second party and vice versa before the parties engage in enciphered communications using a ciphering key provided as a byproduct of the identity-verification process.
The problem of ensuring the security of a communication session, whether the session involves audio, video, or another kind of data, is not a new one. U.S. Pat. No. 4,799,061 to Abraham et al. describes a system for authenticating components in a communication system that is illustrated by FIG. 1. A first party wishing to initiate communication with a second party chooses a random number which is applied at point A with the first party""s secret key as inputs of an enciphering algorithm 1. The first party""s algorithm 1 enciphers the random number according to the secret key, and the resulting enciphered random number is transmitted by the first party to the second party. The second party applies the received enciphered random number with its own secret key as inputs of a deciphering algorithm 2. The deciphering algorithm 2 reproduces at point B the random number applied by the first party at point A only if the second party""s secret key is the same as the first party""s secret key and their algorithms are the same. The second party applies the reproduced random number with its secret key as inputs of the second party""s enciphering algorithm 1. The second party""s algorithm 1 enciphers the second party""s secret key according to the reproduced random number, and the resulting enciphered second party""s secret key is transmitted by the second party to the first party. The first party deciphers the received enciphered second party""s secret key using its random number as the deciphering key in its deciphering algorithm 2. A comparator 3 determines whether the first party""s secret key and the deciphered second party""s secret key are the same; if they are, the first party has authenticated the second party, which in this context is to say that both parties are using the same algorithms and keys. Communication then proceeds using the random number, which both parties now possess, as a ciphering and deciphering key.
The system described in the Abraham patent has a number of disadvantages. In order for the second party to be able to reproduce at point B the same random number inserted by the first party at point A, the transmission from A to B must be xe2x80x9cinformation losslessxe2x80x9d. One of the consequences of information-lossless transmission is that the number of digits of the enciphered random number transmitted from the first party to the second party cannot be less than the number of digits of the random number. If fewer digits were transmitted, there would inevitably be less information transmitted than necessary to reproduce the random number. Indeed, the characteristics of cipher algorithms are such that not even a single digit of the random number would be guaranteed to be reproduced error free at point B unless sufficient information is contained in the enciphered random number.
Furthermore, the Abraham patent uses the random number for enciphering the second party""s key for transmission. If this transmission is intercepted and the random number contains a lower number of digits (i.e., is shorter than) the key, it will be easier for an eavesdropper to crack the ciphering and thereby read the secret key than it would be to crack the secret key itself. Thus, the security of the system is no greater than that determined by the length of the random number. To avoid compromising the degree of security afforded by the secret key, the length of the random number must be greater than or equal to the length of the key, and thus the enciphered random number transmitted from the first party to the second party must also be longer than the key. Choosing a long key for adequate security, however, requires significant transmission time, which is a scarce or expensive resource in some communication systems, for example, cellular telephone systems.
Nevertheless, the need for communication security is acute in flexible systems like cellular telephony. In the United States, losses due to cellular telephone fraud run into the hundreds of millions of dollars, forcing manufacturers, service providers, the Federal Communications Commission (FCC) and industry trade groups to investigate a number of techniques for combating such fraud. One technique involves authenticating both the radio base station and the mobile station, i.e., both ends of a communication link, in order to avoid connection to fraudulent entities.
A simplified layout of a cellular communications system is depicted in FIG. 2. Mobile telephones M1-M10 communicate with the fixed part of a public switched network by transmitting radio signals to, and receiving radio signals from, cellular base stations B1-B10. The cellular base stations B1-B10 are, in turn, connected to the public switched network via a Mobile Switching Center (MSC). Each base station B1-B10 transmits signals within a corresponding area, or xe2x80x9ccellxe2x80x9d C1-C10. As depicted in FIG. 2, an idealized arrangement of base stations are organized so that the cells substantially cover an area in which mobile telephone communication ordinarily occurs (e.g., a metropolitan area), with a minimum amount of overlap.
When a user activates a mobile telephone within a cell, the mobile telephone transmits a signal indicating the mobile telephone""s presence to the cell""s base station. The mobile telephone transmits the signal, which may include its electronic serial number (ESN), in a designated set-up channel that is continuously monitored by each base station. When the base station receives the mobile telephone""s signal, it registers the mobile telephone""s presence within the cell. This process can be repeated periodically so that the mobile telephone is appropriately registered in the event that it moves into another cell.
When a mobile telephone number is dialed, a telephone company central office recognizes the number as a mobile telephone and forwards the call to the MSC. The MSC sends a paging message to certain base stations based on the dialed mobile telephone number and current registration information. One or more of the base stations transmits a page on its set-up channel. The dialed mobile telephone recognizes its identification on the set-up channel, and responds to the base station page. The mobile telephone also follows an instruction to tune to an assigned voice channel and then initiates ringing. When a mobile user terminates a communication, a signaling tone is transmitted to the base station, and both sides release the voice channel.
In the above described operation, mobile telephones are not connected permanently to a fixed network but instead communicate through a so-called xe2x80x9cair interfacexe2x80x9d with a base station. This, of course, provides the flexibility of cellular communication systems, since a user can readily transport a mobile telephone without the restriction of being physically linked to a communication system. This same feature, however, also creates difficulties with respect to securing information transmitted over cellular telephone systems.
For example, in ordinary wired telephone systems, a central office exchange can identify a particular subscriber to be billed for use of a telephone set by the communication line to which it is physically attached. Thus, fraudulent use of a subscriber""s account typically requires that a physical connection be made to the subscriber""s line. This presents a risk of discovery to a would-be fraudulent user.
Cellular telecommunication systems, on the other hand, pose no such connection problem for the would-be fraudulent user since these systems communicate over an air interface. Absent protection schemes, fraudulent users can use another subscriber""s account by accessing the other subscriber""s ESN as it is transmitted to the network at various times for establishing and maintaining communications.
In establishing a standard cellular connection, two identification codes are typically transmitted by a mobile telephone to the system. These are the Mobile Identification Number (MIN) and the ESN. The MIN identifies a subscriber, while the ESN identifies the actual hardware being used by the subscriber. Accordingly, it is expected that the MIN corresponding to a particular ESN can, due to subscribers purchasing new equipment, change over time. The MIN is a 34-bit binary number derived from a 10-digit directory telephone number, while the ESN is a 32-bit binary number that uniquely identifies a mobile telephone. The ESN is typically set by the mobile telephone manufacturer.
A conventional authentication method utilized in setting up communications in, for example, the Advanced Mobile Phone System (AMPS), is illustrated by the flowchart depicted in FIG. 3. According to this method, a base station receives both an ESN and a MIN from the mobile telephone at block 200. These identification codes are designated ESNm and MINm to indicate that they are received from the mobile telephone. Next, at block 202 the base station retrieves an ESNsys which corresponds to MINm from a system memory. ESNsys is then compared with ESNm at block 204. If the two serial numbers are the same, the flow proceeds to block 206 and system access is permitted. Otherwise, system access is denied at block 208.
One drawback to this system is that it is relatively simple for a fraudulent user to assemble valid MIN/ESN combinations by eavesdropping on the air interface or from other sources. Since accesses according to this conventional system are presumed valid if the MIN and ESN received from the mobile telephone correspond with those stored in system memory, all of the necessary information for fraudulent access can be obtained by electronic eavesdropping.
U.S. Pat. No. 5,091,942 to Dent; and U.S. Pat. No. 5,282,250; U.S. Pat. No. 5,390,245; and U.S. Pat. No. 5,559,886, all to Dent et al., are directed to the problem of communication security in systems like cellular telephone systems, and all of these patents are expressly incorporated here by reference. These patents solve the above-mentioned problems with prior cellular telephone methods and the method of the Abraham patent by methods such as that illustrated by FIG. 4.
The first party, who generally would be the party initiating communication, chooses a random number rand and transmits rand to the second party. In addition, the first party uses an authentication algorithm 10 to encipher rand according to the first party""s secret key, generating an enciphered random number having two parts, resp1 and resp2. The first party also transmits resp2 to the second party. The second party enciphers the received rand with its local version of the authentication algorithm 10 according to the second party""s secret key, generating an enciphered random number having two parts, resp1xe2x80x2 and resp2xe2x80x2. The second party uses a comparator 11 to determine whether resp2xe2x80x2 matches resp2; a match indicates to the second party that the first party is probably authentic and merits a reply. The second party""s reply to the first party includes resp1xe2x80x2. The first party uses a comparator 12 to determine whether the received resp1xe2x80x2 matches resp1; a match indicates to the first party that the second party is probably authentic. Such authentication of both ends of a communication can be called bilateral authentication.
In contrast to the prior methods, the lengths of the quantities rand, resp2, and resp1xe2x80x2 that are exchanged by the parties are not critical to the security of the system depicted in FIG. 4. In fact, they may have fewer digits than the secret keys. The numbers of digits need only be sufficient that a second party not in possession of the same secret key as the first party has a negligible probability by chance of getting resp1xe2x80x2 equal to the value resp1 expected by the first party and that the first party has a negligible probability by chance of getting a value resp2 equal to the value of resp2xe2x80x2 that will be computed by the second party. For example if resp1 and resp2 both have sixteen binary digits (bits), the chances are only 1/65,536 of getting such a value right by accident, which is sufficiently low to render a guessing game unprofitable for many useful communication systems. Moreover, using a combined length of resp1 and resp2 that is much shorter than the length of the secret key means that insufficient information is transmitted to permit a unique determination of the key, even if sufficient computing power is available to try all possible keys. Even so, the method of FIG. 4 leaves one at liberty to choose long keys to make such computation impractical, without incurring the transmission time overhead of exchanging long authentication quantities between the parties.
On the other hand, the method of FIG. 4 might be weakened if an eavesdropper can collect several sets of rand, resp2 pairs from a genuine first party that could then be used to address a genuine second party or to attempt to crack the secret key. The patents incorporated by reference above disclose ways of hindering the latter weakness, including the use of rolling keys. U.S. patent application Ser. No. 08/706,574 by Osborn for a xe2x80x9cSystem for Preventing Electronic Memory Tamperingxe2x80x9d addresses the former weakness, and is expressly incorporated here by reference.
It is, however, still important to improve the security of bilateral authentication procedures while keeping transmission overhead to a minimum. These objectives or advantages are obtained when practicing the authentication methods described in this application.
A first party wishing to initiate communications with a second party generates a random number comprising a first number of digits. The first party then enciphers the random number using a secret ciphering key to obtain an enciphered version of the random number comprising a second number of digits greater or equal to the first number. A third number of selected digits of the enciphered random number are then transmitted to the second party, where the third number is less than the first number.
The second party receives the digits transmitted from the first party and expands the third number of digits in a pre-agreed manner to obtain the second number of digits. The expansion process can be as simple as padding out the third number of digits with constant digits such as zeros.
The second party then deciphers the so-obtained second number digits using the second party""s secret key to obtain the first number of digits, which is not equal to the original random number chosen by the first party. The so-obtained first number of digits is then used by the second party as a ciphering key to encipher the second party""s secret key thereby obtaining an enciphered key containing the second number of digits. A fourth number of digits less than the second number are then selected by the second party and transmitted to the first party.
The first party also expands the third number of digits it transmitted to the first party in the same pre-agreed manner to obtain the second number of digits and then deciphers this so-obtained second number of digits using its secret key to obtain a first number of digits once more. The first party then selects from these a fourth number of digits less than the second number in the same manner as the second party, and compares the selected fourth number of selected digits with the fourth number of digits received from the second party. If a complete match is detected, the first party has verified that the second party possesses the same secret key as itself.
The roles may then be reversed to allow the second party to verify the identity of the first party, either by repeating the above procedure starting with a new random number chosen by the second party, or else continuing to derive a number of digits to be returned from the first party to the second party based on the digits received from the second party and the first party""s secret key.
In a more general implementation of the above, the steps of selecting a smaller number of digits from a larger number of digits may be replaced by a step of generating a smaller number of digits from a larger number of digits using a pre-agreed compression algorithm, which can also depend on the secret key available to the party performing the compression.
In addition, if savings in computational effort are thereby achieved, whenever a smaller number of digits only are needed, the larger number of digits do not all need to be generated.